#include <iostream>

#define MAX_CHILD 3

using namespace std;

typedef char DATATYPE;

struct forest {
	DATATYPE data;
	int count;
	forest* parent;
	forest** child;

	forest() :count(0), parent(nullptr), child(new forest*[MAX_CHILD])
	{
		for (int i = 0; i < MAX_CHILD; i++) child[i] = nullptr;
	}
};

bool isAlpha(char ch) {
	if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
		return true;
	else
		return false;
}

void create_forest(char* &s, forest* root) {
	char ch = *s++;

	if (ch == '\0') return;

	if (isAlpha(ch)) {
		forest* p = new forest;
		p->data = ch;
		p->parent = root;
		root->child[root->count++] = p;
		create_forest(s, root);
	}
	else if (ch == '(') {
		root = root->child[root->count - 1];
		create_forest(s, root);
	}
	else if (ch == ')') {
		root = root->parent;
		create_forest(s, root);
	}
}

void forest_to_btree(forest* root) {
	//return if root has no child at all
	if (!root->child[0]) return;

	for (int i = 0; i < MAX_CHILD; i++) {
		if (!root->child[i]) continue;
		forest_to_btree(root->child[i]);
	}

	for (int i = MAX_CHILD - 1; i > 0; i--) {
		if (!root->child[i]) continue;
		root->child[i - 1]->child[1] = root->child[i];
		root->child[i - 1]->count++;
		root->child[i] = nullptr;
		root->count--;
	}
}

/* split the right side first, and then
convert the sub-tree in the left */
void btree_to_forest(forest* root) {
	//return if root has no left child
	if (!root->child[0]) return;

	forest* lchild = root->child[0];
	forest* rchild = lchild->child[1];
	if (lchild->child[1]) {
		lchild->child[1] = nullptr;
		lchild->count--;
	}
	while (rchild) {
		root->child[root->count++] = rchild;
		forest* temp = rchild;
		rchild = rchild->child[1];
		if (temp->child[1]) {
			temp->child[1] = nullptr;
			temp->count--;
		}
		btree_to_forest(temp);
	}

	btree_to_forest(lchild);
}

void preorder_traverse(forest* root) {
	if (root) {
		cout << root->data << '(';
		for (int i = 0; i < 2; i++) {
			if (root->child[i]) cout << root->child[i]->data;
			else cout << '#';
		}
		cout << ')' << endl;
		preorder_traverse(root->child[0]);
		preorder_traverse(root->child[1]);
	}
}

void _preorder_traverse_tree(forest* root) {
	if (root) {
		cout << root->data << '(';
		for (int i = 0; i < 3; i++) {
			if (root->child[i]) cout << root->child[i]->data;
			else cout << '#';
		}
		cout << ')' << endl;
		for (int i = 0; i < MAX_CHILD; i++) {
			_preorder_traverse_tree(root->child[i]);
		}
	}
}

void preorder_traverse_forest(forest* f) {
	for (int i = 0; i < MAX_CHILD; i++) {
		_preorder_traverse_tree(f->child[i]);
	}
}

void delete_forest(forest* f) {
	if (f->child[0] == nullptr) return;

	for (int i = 0; i < MAX_CHILD; i++) {
		if (!f->child[i]) break;
		delete_forest(f->child[i]);

		delete f->child[i];
		f->child[i] = nullptr;
	}

}

void delete_btree(forest* btree) {
	if (!btree) return;

	for (int i = 0; i < 2; i++) {
		if (btree->child[i]) {
			delete btree->child[i];
			btree->child[i] = nullptr;
		}
	}
}

int main() {
	char s[] = "A(BCD)E(F)G(H(I)J)";
	char *p = s;

	forest* f = new forest;
	create_forest(p, f);

	forest_to_btree(f);
	preorder_traverse(f->child[0]);

	cout << endl;

	btree_to_forest(f);
	preorder_traverse_forest(f);

	delete_forest(f);

	return 0;
}
